const arr1 = [1, 2, 8, 4, 22, 12];

const quickSort1 = (arr: Array<number>) => {
  // 缓存数组的长度
  const len = arr.length;
  if (len === 0) return arr;
  // 寻找中间值索引
  const midIndex = Math.floor(len / 2);
  // 寻找中间值
  const mid = arr.slice(midIndex, midIndex + 1)[0];
  // left
  const left: Array<number> = [];
  // 定义右边数组
  const right: Array<number> = [];
  for (let index = 0; index < len; index++) {
    const n = arr[index];
    // 比mid小的放在左边数组
    if (n < mid) left.push(n);
    if (n > mid) right.push(n);
  }
  // 使用递归继续推left和right数组,最后拼接
  return quickSort1(left).concat(mid,quickSort1(right))
};
